package 长度最小的子数组;

public class MinSubArrayLen {
    public static void main(String[] args) {
        /*

        给定一个含有 n 个正整数的数组和一个正整数 target 。
        找出该数组中满足其总和大于等于 target 的长度最小的子数组
        [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0

         */

        int[] nums = {2,3,1,2,4,3};
        System.out.println(minSubArrayLen(7, nums));

    }

    public static int minSubArrayLen(int target, int[] nums){
        // 使用双指针解决（滑动窗口）
        // 1.利用一个for循环中的索引标记当前窗口的结束位置（这样就避免了暴力解法不知道哪里结束的弊端）一个元素最多被遍历两次
        // 2.一个窗口内，sum大了我们就利用起始位置的移动来缩小范围，sum小了我们就利用结束位置的移动来缩小范围
        // 3.窗口内是什么？：窗口内就是满足 sum >= target 的长度最小的连续子数组

        // 最小连续子数组的长度
        int minLength = nums.length;
        // 窗口的左端
        int left = 0;
        // 窗口内的连续子数组的总和
        int sum = 0;
        for (int right = 0; right < nums.length; right++) {
            sum = sum + nums[right];
           while ( sum >= target ){
               minLength = Math.min(minLength, right - left + 1);
               sum = sum - nums[left];
               left++;
           }
        }

        return minLength == nums.length ? 0 : minLength;

    }
}
